import numpy as np
import pickle

class SVM:
    def __init__(self, dataSet, labels, C, toler, kernel_option):
        self.train_x = dataSet
        self.train_y = labels
        self.C = C
        self.toler = toler
        self.n_samples = np.shape(dataSet)[0]
        self.alphas = np.mat(np.zeros((self.n_samples, 1)))
        self.b = 0
        self.error_tmp = np.mat(np.zeros((self.n_samples, 2)))
        self.kernel_opt = kernel_option
        self.kernel_mat = calc_kernel(self.train_x, self.kernel_opt)

def calc_kernel(train_x, kernel_option):
    '''
    计算函数的矩阵
    :param train_x: 训练样本的特征值
    :param kernel_option: 该函数的类型以及参数
    :return: 样本的核函数的值
    '''
    m = np.shape(train_x)[0]
    kernel_matrix = np.mat(np.zeros((m, m)))
    for i in range(m):
        kernel_matrix[:, i] = cal_kernel_value(train_x, train_x[i, :], kernel_option)
    return kernel_matrix

def cal_kernel_value(train_x, train_x_i, kernel_option):
    '''
    样本之间核函数的值
    :param train_x:训练样本
    :param train_x_i:第i个训练样本
    :param kernel_option: 核函数的类型以及参数
    :return: 样本之间的核函数的值
    '''
    kernel_type = kernel_option[0]
    m = np.shape(train_x)[0]

    kernel_value = np.mat(np.zeros((m, 1)))

    if kernel_type == 'rbf':
        sigma = kernel_option[1]
        if sigma == 0:
            sigma = 1.0
        for i in range(m):
            diff = train_x[i, :] -train_x_i
            kernel_value[i] = np.exp(diff * diff.T / (-2 * sigma ** 2))
    else:
        kernel_value = train_x * train_x_i.T
    return kernel_value

def SVM_training(train_x, train_y, C, toler, max_iter, kernel_option = ('rbf', 0.431029)):
    '''
    SVM的训练
    :param train_x:训练数据的特征
    :param train_y: 训练数据的标签
    :param C: 惩罚系数
    :param toler: 迭代的终止条件之一
    :param max_iter: 最大迭代次数
    :param kernel_option: 核函数的类型及参数
    :return: svm模型
    '''

    svm = SVM(train_x, train_y, C, toler, kernel_option)

    entireSet = True
    alpha_pairs_changed = 0
    iteration = 0

    while (iteration < max_iter) and ((alpha_pairs_changed > 0) or entireSet):
        print("\t iterration: ", iteration)
        alpha_pairs_changed = 0

        if entireSet:

            for x in range(svm.n_samples):
                alpha_pairs_changed += choose_and_update(svm, x)
            iteration += 1
        else:

            bound_samples = []
            for i in range(svm.n_samples):
                if svm.alphas[i, 0] > 0 and svm.alphas[i, 0] < svm.C:
                    bound_samples.append(i)
            for x in bound_samples:
                alpha_pairs_changed += choose_and_update(svm, x)
            iteration += 1

        if entireSet:
            entireSet = False
        elif alpha_pairs_changed == 0:
            entireSet = True

    return svm

def choose_and_update(svm, alpha_i):
    '''
    判断和选择两个alpha进行更新
    :param svm: svm模型
    :param alpha_i: 选择出的第一个变量
    '''
    error_i = cal_error(svm, alpha_i)

    if(svm.train_y[alpha_i] * error_i < -svm.toler and svm.alphas[alpha_i] < svm.C or
            svm.train_y[alpha_i] * error_i * error_i > svm.toler and svm.alphas[alpha_i] > 0):

        alpha_j, error_j = select_second_sample_j(svm, alpha_i, error_i)
        alpha_i_old = svm.alphas[alpha_i].copy()
        alpha_j_old = svm.alphas[alpha_j].copy()

        if svm.train_y[alpha_i] != svm.train_y[alpha_j]:
            L = max(0, svm.alphas[alpha_j] - svm.alphas[alpha_i])
            H = min(svm.C, svm.C + svm.alphas[alpha_j] - svm.alphas[alpha_i])
        else:
            L = max(0, svm.alphas[alpha_j] + svm.alphas[alpha_i] -svm.C)
            H = min(svm.C, svm.alphas[alpha_j] + svm.alphas[alpha_i])
        if L == H:
            return 0

        eta = 2.0 * svm.kernel_mat[alpha_i, alpha_j] - svm.kernel_mat[alpha_i, alpha_i] - svm.kernel_mat[alpha_j, alpha_j]
        if eta >= 0:
            return 0

        svm.alphas[alpha_j] -= svm.train_y[alpha_j] * (error_i - error_j) / eta

        if svm.alphas[alpha_j] > H:
            svm.alphas[alpha_j] = H
        if svm.alphas[alpha_j] < L:
            svm.alphas[alpha_j] = L

        if abs(alpha_j_old - svm.alphas[alpha_j]) < 0.00001:
            update_error_tmp(svm, alpha_j)
            return 0

        svm.alphas[alpha_i] += svm.train_y[alpha_i] * svm.train_y[alpha_j] * (alpha_j_old - svm.alphas[alpha_j])

        b1 = svm.b - error_i - svm.train_y[alpha_i] * (svm.alphas[alpha_i] - alpha_i_old) * svm.kernel_mat[alpha_i, alpha_i] \
             - svm.train_y[alpha_j] * (svm.alphas[alpha_j] - alpha_j_old) * svm.kernel_mat[alpha_i, alpha_j]
        b2 = svm.b - error_i - svm.train_y[alpha_i] * (svm.alphas[alpha_i] - alpha_i_old) * svm.kernel_mat[alpha_i, alpha_j] \
             - svm.train_y[alpha_j] * (svm.alphas[alpha_j] - alpha_j_old) * svm.kernel_mat[alpha_j, alpha_j]
        if 0 < svm.alphas[alpha_i] and svm.alphas[alpha_i] < svm.C:
            svm.b = b1
        elif 0 < svm.alphas[alpha_j] and svm.alphas[alpha_j] < svm.C:
            svm.b = b2
        else:
            svm.b = (b1 + b2) / 2.0

        update_error_tmp(svm, alpha_j)
        update_error_tmp(svm, alpha_i)

        return 1
    else:
        return 0

def cal_error(svm, alpha_k):
    '''
    误差值的计算
    :param svm:svm模型
    :param alpha_k: 选择出的变量
    :return: 误差值
    '''
    output_k = float(np.multiply(svm.alphas, svm.train_y).T * svm.kernel_mat[:, alpha_k] + svm.b)
    error_k = output_k - float(svm.train_y[alpha_k])
    return error_k

def select_second_sample_j(svm, alpha_i, error_i):
    '''
    选择第二个版本
    :param svm: svm模型
    :param alpha_i: 选择出的第一个变量
    :param error_i: E_i
    :return: alpha_j: 选择出的第二个变量 error_j: E_j
    '''

    svm.error_tmp[alpha_i] = [1, error_i]
    candidateAlphaList = np.nonzero(svm.error_tmp[:, 0].A)[0]

    maxStep = 0
    alpha_j = 0
    error_j = 0

    if len(candidateAlphaList) > 1:
        for alpha_k in candidateAlphaList:
            if alpha_k == alpha_i:
                continue
            error_k = cal_error(svm, alpha_k)
            if abs(error_k - error_i) > maxStep:
                maxStep = abs(error_k - error_i)
                alpha_j = alpha_k
                error_j = error_k
    else:
        alpha_j = alpha_i
        while alpha_j == alpha_i:
            alpha_j = int(np.random.uniform(0, svm.n_samples))
        error_j = cal_error(svm, alpha_j)

    return alpha_j, error_j

def update_error_tmp(svm, alpha_k):
    '''
    重新计算误差
    :param svm: svm模型
    :param alpha_k: 选择出的变量
    :return: 对应误差值
    '''
    error = cal_error(svm, alpha_k)
    svm.error_tmp[alpha_k] = [1, error]

def cal_accuracy(svm, test_x, test_y):
    '''
    计算预测准确性
    :param svm: svm模型
    :param test_x: 测试的特征
    :param test_y: 测试的标签
    :return: 预测的准确性
    '''
    n_samples = np.shape(test_x)[0]
    correct = 0.0
    for i in range(n_samples):

        predict = svm_predict(svm, test_x[i, :])

        if np.sign(predict) == np.sign(test_y[i]):
            correct += 1
    accuracy = correct / n_samples
    return accuracy

def svm_predict(svm, test_sample_x):
    '''
    利用svm模型对每一个样本进行预测
    :param svm: svm模型
    :param test_sample_x:样本
    :return: 对样本的预测
    '''

    kernel_value = cal_kernel_value(svm.train_x, test_sample_x, svm.kernel_opt)

    predict = kernel_value.T * np.multiply(svm.train_y, svm.alphas) + svm.b
    return predict

def save_svm_model(svm_model, model_file):
    '''
    :param svm_model:svm模型
    :param model_file: svm模型需要保存到的文件
    :return:
    '''
    with open(model_file, 'wb') as f:
        pickle.dump(svm_model, f)